Base \(10\) Divisibility Rules

A divisibility rule is a short rule or algorithm that can be used to determine (generally integral) divisibility. Here is a list of many divisibility rules based on the digits of integers in their base \(10\) representation and corresponding proofs.

Throughout these proofs, let \(k = a_n 10^n + a_{n - 1}10^{n - 1} + \dots + a_1 10 + a_0\) be the base \(10\) representation of a non-negative integer \(k\) such that \(a_i \in \{ 1, \dots, 9 \}\) are the digits.

Each of these rules is only provided for non-negative integers, however most of them generalise to any integer. Rules that don't include that of \(7\), however in cases like this, divisibility for a negative number should be checked by verifying divisibility for its absolute value, since \(m \mid k \iff m \mid -k\).

Also note we only prove rules for divisibility by prime powers since for example checking divisibility by \(12\) reduces to checking divisibility by \(3\) and \(4\). The same is true for any integer which is not the power of a prime.

2

Theorem

A natural number is divisible by \(2\) if and only if its last digit is divisible by \(2\).

Proof

Since \(2 \mid 10\), we have that

\[ k = 2(a_n 5^n + a_{n - 1}5^{n - 1} + \dots + a_1 5) + a_0\]

and therefore

\[ k \equiv a_0 \pmod 2\]

which implies that

\[ 2 \mid k \iff k \equiv 0 \pmod 2 \iff a_0 \equiv 0 \pmod 2 \iff 2 \mid a_0.\]

3

Theorem

A natural number is divisible by \(3\) if and only if the sum of its digits is divisible by \(3\).

Proof

Consider that

\[\begin{align*} k &= a_n (10^n - 1) + a_n + a_{n - 1}(10^{n - 1} - 1) + a_{n - 1} + \dots + a_1 (10 - 1) + a_1 + a_0 \\ &= \left(\sum_{i = 0}^n a_i\right) + a_n (10^n - 1) + a_{n - 1}(10^{n - 1} - 1) + a_{n - 1} + \dots + a_1 (10 - 1) + a_1. \\ \end{align*}\]

From here it is clear that \(10^r - 1 \equiv 1^r - 1 \equiv 0 \pmod 3\) for all \(r \geq 0\), and therefore

\[ k \equiv \sum_{i = 0}^n a_i \pmod 3\]

which implies that

\[ 3 \mid k \iff k \equiv 0 \pmod 3 \iff \sum_{i = 0}^n a_i \equiv 0 \pmod 3 \iff 3 \mid \sum_{i = 0}^n a_i.\]

4

Theorem

A natural number is divisible by \(4\) if and only if the two digit number formed from its last two digits is divisible by \(4\).

Proof

Since \(4 \mid 100\) given \(4 \times 25 = 100\), we have that

\[ k = 4 \times 25 (a_n 10^{n - 2} + a_{n - 1}10^{n - 3} + \dots + a_2) + a_1 10 + a_0\]

and therefore

\[ k \equiv a_1 10 + a_0 \pmod 4\]

which implies that

\[ 4 \mid k \iff k \equiv 0 \pmod 4 \iff a_1 10 + a_0 \equiv 0 \pmod 4 \iff 4 \mid a_1 10 + a_0.\]

5

Theorem

A natural number is divisible by \(5\) if and only if its last digit is \(0\) or \(5\).

Proof

As \(5\) is a factor of \(10\), this proof follows almost identically to the divisibility rule for \(2\). In particular we have that

\[ k = 5(a_n 2^n + a_{n - 1}2^{n - 1} + \dots + a_1 2) + a_0\]

and therefore

\[ k \equiv a_0 \pmod 5\]

which implies that

\[ 5 \mid k \iff k \equiv 0 \pmod 5 \iff a_0 \equiv 0 \pmod 5 \iff 5 \mid a_0.\]

7

Theorem

A natural number is divisible by \(7\) if and only if the number formed by doubling the last digit and subtracting that from the truncated number is divisible by \(7\).

Since this rule is a little weirder, here is an example.

Example

\(3976\) is divisible by \(7\).

Solution

We take the truncated number \(397\) and subtract twice the last digit to get \(397 - 6 \cdot 2 = 385\). Repeating this, we have \(38 - 5 \cdot 2 = 28\). Again, we have \(2 - 8 \times 2 = -14\) and finally \(1 - 4 \cdot 2 = -7\), which is clearly divisible by \(7\).

Proof
\[\begin{align*} & k \equiv 0 \pmod 7 \\ \iff& a_n 10^n + a_{n - 1}10^{n - 1} + \dots + a_1 10 + a_0 \equiv 0 \pmod 7 \\ \iff& 10(a_n 10^{n - 1} + a_{n - 1}10^{n - 2} + \dots + a_1) \equiv - a_0 \pmod 7 \\ \iff& a_n 10^{n - 1} + a_{n - 1}10^{n - 2} + \dots + a_1 \equiv - 10^{-1} a_0 \pmod 7 \\ \iff& (a_n 10^{n - 1} + a_{n - 1}10^{n - 2} + \dots + a_1) - 2a_0 \equiv - 10^{-1} a_0 - 2a_0 \pmod 7 \\ \iff& (a_n 10^{n - 1} + a_{n - 1}10^{n - 2} + \dots + a_1) - 2a_0 \equiv -(10^{-1} + 2)a_0 \pmod 7 \\ \iff& (a_n 10^{n - 1} + a_{n - 1}10^{n - 2} + \dots + a_1) - 2a_0 \equiv 0 \pmod 7 \\ \end{align*}\]

where this last equivalence holds because \(10 \times -2 = -20 \equiv 1 \pmod 7\) which implies that \(10^{-1} = -2\) in \(\mathbb{Z}_7\) and subsequently \(10^{-1} + 2 \equiv 0 \pmod 7\).